#define _CRT_SECURE_NO_WARNINGS 

//#include<iostream>
//using namespace std;
//int p[110];
//int n, q;
//
//
//int main()
//{
//	cin >> n >> q;
//	while (q--)
//	{
//		int f, w;
//		cin >> f >> w;
//		if (f == 3)
//		{
//			if (p[w] >= 2)
//				cout << "Yes" << endl;
//			else
//				cout << "No" << endl;
//			continue;
//		}
//		p[w] += f;
//	}
//	return 0;
//}

//#include<iostream>
//#include<queue>
//#include<cmath>
//using namespace std;
//priority_queue<int, vector<int>, less<int>>heap;
//
//int main()
//{
//	int n, p, q;
//	cin >> n >> p >> q;
//	for (int i = 0; i < n; i++)
//	{
//		int a;
//		cin >> a;
//		heap.push(a);
//	}
//
//	while (q > 0 || p > 0)
//	{
//		int t = heap.top();
//		heap.pop();
//		if (p > 0)
//		{
//			int t1 = pow(t, 0.5);
//			heap.push(t1);
//			continue;
//		}
//		int t2 = t / 2;
//		heap.push(t2);
//	}
//	while(
//	return 0;
//}

//#include<iostream>
//using namespace std;
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		int flag = 0;
//		string s;
//		cin >> s;
//		char c;
//		cin >> c;
//		for (int i = 0; i < s.size(); i++)
//		{
//			if (s[i] == c&&i%2==0)
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag)
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	}
//	return 0;
//}

//#include<iostream>
//using namespace std;
//
//int fun(int x, int p)
//{
//	return x / p + x % p;
//}
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		int l, r, a;
//		cin >> l >> r >> a;
//
//		int e1 = fun(r, a);
//		int f = r- r % a - 1;
//		int e2 = 0;
//		if(f>=l)
//			e2 = fun(f, a);
//
//		cout << max(e1, e2) << endl;
//	}
//	return 0;
//}


//#include<iostream>
//#include<algorithm>
//#include<vector>
//using namespace std;
//const int N = 2e5 + 10;
//
//struct trip {
//	int _a, _b, _idx;
//
//	bool operator<(const trip& w)const {
//		return _b < w._b;
//	}
//}trip[N];
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		int n, m;
//		cin >> n >> m;
//		for (int i = 0; i < m; i++)
//		{
//			int a, b;
//			cin >> a >> b;
//			trip[i] = { a,b,i + 1 };
//		}
//		sort(trip, trip + m);
//		long long ans = 0;
//		for (int i = 0; i < 2 * n; i++)
//		{
//			ans += trip[i]._b;
//		}
//
//		cout << ans << endl;
//		vector<pair<int, int>>ma;
//		for (int i = 0; i < 2 * n; i++)
//		{
//			ma.push_back({ trip[i]._a,trip[i]._idx });
//		}
//		sort(ma.begin(), ma.end());
//		for (int i = 0; i < n; i++)
//			cout << ma[i].second << " " << ma[2 * n - i - 1].second << endl;
//
//	}
//	return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 2e3 + 10;
//int a[N];
//int f[N];
//
//int main()
//{
//	int t;
//	cin >> t;
//	while (t--)
//	{
//		int n;
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			int x; cin >> x;
//			a[x] = i;
//		}
//		for (int i = n; i >= 1; i--)
//		{
//			int tt = a[i];
//			int yy = a[i] % i;
//			f[i] = yy;
//			for (int j = 1; j <= i; j++)
//			{
//				if (a[j] - yy >= 0)
//					a[j] = a[j] - yy;
//				else
//					a[j] = ( a[j] - yy + i) % n;
//			}
//		}
//		for (int i = 1; i <= n; i++)
//			cout << f[i] << " ";
//		cout << endl;
//	}
//
//	return 0;
//}

